#include <iostream>
#include <vector>
#include <climits> 
class Solution {
public:
    int findKthPositive(std::vector<int>& arr, int k) {
        if (arr[0] > k) {
            return k;
        }  
        int l = 0, r = arr.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            int x = mid < arr.size() ? arr[mid] : INT_MAX;
            if (x - mid - 1 >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return k - (arr[l-1] - (l-1) - 1) + arr[l - 1];
    }
};

int main() {
    Solution sol;
    int test1[] = {2, 3, 4, 7, 11};
    std::vector<int> arr1(test1, test1 + sizeof(test1)/sizeof(test1[0]));
    int k1 = 5;
    std::cout << "Test1: " << sol.findKthPositive(arr1, k1) << " (Expected: 9)\n";
    int test2[] = {4, 5, 6};
    std::vector<int> arr2(test2, test2 + sizeof(test2)/sizeof(test2[0]));
    int k2 = 3;
    std::cout << "Test2: " << sol.findKthPositive(arr2, k2) << " (Expected: 3)\n";
    int test3[] = {1, 2, 3};
    std::vector<int> arr3(test3, test3 + sizeof(test3)/sizeof(test3[0]));
    int k3 = 5;
    std::cout << "Test3: " << sol.findKthPositive(arr3, k3) << " (Expected: 8)\n";
    std::vector<int> arr4;
    int k4 = 7;
    std::cout << "Test4: " << sol.findKthPositive(arr4, k4) << " (Expected: 7)\n";
    
    return 0;
}
